#pragma once

#include <string>
#include <vector>

namespace solution_010
{

class Solution
{
public:
    bool isMatch(std::string s, std::string p)
    {
        int m = s.size();
        int n = p.size();

        std::vector table(m + 1, std::vector(n + 1, 0));
        table[0][0] = true;

        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j-1] == '*') {
                    if ( i > 0 && (p[j-2] == '.' || p[j-2] == s[i-1]) ) {
                        /* match zero or match 2 */
                        table[i][j] = table[i][j-2] || table[i-1][j];
                    } else {
                        /* match zero */
                        table[i][j] = table[i][j-2];
                    }
                } else {
                    if ( i > 0 && (p[j-1] == '.' || s[i-1] == p[j-1]) )
                        table[i][j] = table[i-1][j-1];
                }
            }
        }

        return table.back().back();
    }
};

}  /* namespace solution_010 */
